package com.practice.sequence;

import java.util.ArrayDeque;

/**
 * A long array A[] is given to you. There is a sliding window of size w 
 * which is moving from the very left of the array to the very right. 
 * You can only see the w numbers in the window. Each time the sliding 
 * window moves rightwards by one position.
 * 
 * Input: 		A long array A[], and a window width w
 * Output: 		An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
 * Requirement: Find a good optimal way to get B[i]
 *
 */
public class SlidingWindowMaximum {
	public int[] getWindowMax(int[] a, int w) {
		int[] b = new int[a.length - w + 1];
		
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		for (int i=0; i<w; i++) {
			while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
			q.addLast(i);
		}
		
		b[0] = a[q.peekFirst()];
		for (int i=w; i<a.length; i++) {
			while (!q.isEmpty() && q.peekFirst()<=i-w) q.pop();
			while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
			q.addLast(i);
			b[i-w+1] = a[q.peekFirst()];
		}
		
		return b;
	}
}
